package leetcodev1.数组;

import java.util.ArrayList;
import java.util.List;

public class LeetCode78 {

    //回溯 选或者不选
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        helper(nums, ret, 0, new ArrayList<>());
        return ret;
    }

    private void helper(int[] nums, List<List<Integer>> ret, int index, List<Integer> router) {
        if (index == nums.length) {
            ret.add(new ArrayList<>(router));
            return;
        }

        //选择
        router.add(nums[index]);
        helper(nums, ret, index + 1, router);
        //不选择
        router.remove(router.size() - 1);
        helper(nums, ret, index + 1, router);
    }

    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    //将取或者不取 根据1|0来判断
    //枚举出所有的情况 不需要递归
    public List<List<Integer>> subsets1(int[] nums) {
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();//清空
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}
